/*!
 Temelia - Scapegoat tree implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/scapegoat_tree.h"
#include <stdlib.h>

struct _scapegoat_tree_t
{
	/*! Reference to scapegoat tree's root */
	scapegoat_node_t root;

	/*! alpha parameter */
	double alpha;

	/*! scapegoat's current size */
	int size;

	/*! scapegoat's maximum size */
	int max_size;
};

static void _scapegoat_tree_rebalance();

scapegoat_tree_t scapegoat_tree_new(double alpha)
{
	scapegoat_tree_t scapegoat;

	_ASSERT(alpha, <, 0.5, INVALID_INPUT, NULL);
	_ASSERT(alpha, >, 1, INVALID_INPUT, NULL);

	scapegoat = (struct _scapegoat_tree_t *) _new(
			sizeof(struct _scapegoat_tree_t));

	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, NULL);

	scapegoat->root = NULL;
	scapegoat->alpha = alpha;
	scapegoat->size = scapegoat->max_size = 0;

	return scapegoat;
}

void scapegoat_tree_delete_node(scapegoat_node_t scapegoat)
{
	_binary_tree_delete_node(scapegoat);
}

void scapegoat_tree_delete(scapegoat_tree_t scapegoat)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER,);

	if (scapegoat->size > 0)
		_binary_tree_delete(scapegoat->root);

	scapegoat->root = NULL;
	scapegoat->alpha = 0;
	scapegoat->size = scapegoat->max_size = 0;

	_delete(scapegoat);
}

int scapegoat_tree_compare_trees(scapegoat_tree_t scapegoat1,
		scapegoat_tree_t scapegoat2, int compare(void *x, void *y,
				void *context), void *context)
{
	_ASSERT(scapegoat1, ==, NULL, NULL_POINTER, -1);
	_ASSERT(scapegoat2, ==, NULL, NULL_POINTER, -1);

	return _binary_tree_compare_trees(scapegoat1->root, scapegoat2->root,
			compare, context);
}

int scapegoat_tree_is_empty(scapegoat_tree_t scapegoat)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, -1);

	return scapegoat->root == NULL;
}

int scapegoat_tree_is_leaf(scapegoat_node_t scapegoat)
{
	return _binary_tree_leaf(scapegoat);
}

int scapegoat_tree_get_size(scapegoat_tree_t scapegoat)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, -1);

	return scapegoat->size;
}

double scapegoat_tree_get_alpha(scapegoat_tree_t scapegoat)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, -1);

	return scapegoat->alpha;
}

scapegoat_node_t scapegoat_tree_get_root(scapegoat_tree_t scapegoat)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, NULL);

	return scapegoat->root;
}

scapegoat_node_t scapegoat_tree_get_node_root(scapegoat_node_t scapegoat)
{
	return _binary_tree_get_root(scapegoat);
}

void *scapegoat_tree_get_key(scapegoat_node_t scapegoat)
{
	return _binary_tree_get_key(scapegoat);
}

scapegoat_node_t scapegoat_tree_get_parent(scapegoat_node_t scapegoat)
{
	return _binary_tree_get_parent(scapegoat);
}

scapegoat_node_t scapegoat_tree_get_left_child(scapegoat_node_t scapegoat)
{
	return _binary_tree_get_left_child(scapegoat);
}

scapegoat_node_t scapegoat_tree_get_right_child(scapegoat_node_t scapegoat)
{
	return _binary_tree_get_right_child(scapegoat);
}

int scapegoat_tree_get_height(scapegoat_tree_t scapegoat)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, -1);

	return _binary_tree_get_height(scapegoat->root);
}

int scapegoat_tree_get_node_height(scapegoat_node_t scapegoat)
{
	return _binary_tree_get_height(scapegoat);
}

int scapegoat_tree_get_depth(scapegoat_node_t scapegoat)
{
	return _binary_tree_get_depth(scapegoat);
}

scapegoat_node_t scapegoat_tree_search(scapegoat_tree_t scapegoat, void *key,
		int compare(void *x, void *y, void *context), void *context)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, NULL);

	return _binary_search_tree_search(scapegoat->root, key, compare, context);
}

scapegoat_node_t scapegoat_tree_insert(scapegoat_tree_t scapegoat, void *key,
		int compare(void *x, void *y, void *context), void *context)
{
	scapegoat_node_t add = NULL;

	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, NULL);

	if (scapegoat->root == NULL)
	{
		scapegoat->root = _binary_tree_new(key);
		scapegoat->size = 1;
		return scapegoat->root;
	}

	/*
	 * The algorithm is:
	 * 	insert the key as in a binary search tree
	 * 	start tree balancing using scapegoat technique, from the new added node.
	 */
	add = _binary_search_tree_insert(scapegoat->root, key, compare, context);

	if (add)
	{
		_scapegoat_tree_rebalance(scapegoat, add);
		scapegoat->size++;
	}

	return add;
}

scapegoat_node_t scapegoat_tree_remove(scapegoat_tree_t scapegoat, void *key,
		int compare(void *x, void *y, void *context), void *context)
{
	scapegoat_node_t deleted = NULL, replaced = NULL;

	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(scapegoat->size, <=, 0, EMPTY, NULL);

	/*
	 * The algorithm is :
	 * 	delete the key as in a normal binary search tree
	 * 	if size < max_size * alpha then
	 * 		start tree rebalancing using scapegoat technique, from the replaced node
	 * If size = max_size then (1-alpha)*max_size deletes need no balance.
	 */
	replaced = _binary_search_tree_remove(&(scapegoat->root), key, compare,
			context, &deleted);

	if (scapegoat->size < scapegoat->max_size * scapegoat->alpha)
		_scapegoat_tree_rebalance(scapegoat, replaced);

	if (deleted)
		scapegoat->size--;

	_binary_tree_delete_node(deleted);

	return replaced;
}

scapegoat_node_t scapegoat_tree_get_min(scapegoat_tree_t scapegoat)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(scapegoat->size, <=, 0, EMPTY, NULL);

	return _binary_search_tree_get_min(scapegoat->root);
}

scapegoat_node_t scapegoat_tree_get_max(scapegoat_tree_t scapegoat)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(scapegoat->size, <=, 0, EMPTY, NULL);

	return _binary_search_tree_get_max(scapegoat->root);
}

void scapegoat_tree_preorder(scapegoat_tree_t scapegoat, void key_handler(
		void *x, void *context), void *context)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER,);
	_ASSERT(scapegoat->size, <=, 0, EMPTY,);

	_binary_tree_preorder(scapegoat->root, key_handler, context);
}

void scapegoat_tree_inorder(scapegoat_tree_t scapegoat, void key_handler(
		void *x, void *context), void *context)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER,);
	_ASSERT(scapegoat->size, <=, 0, EMPTY,);

	_binary_tree_inorder(scapegoat->root, key_handler, context);
}

void scapegoat_tree_reverse_inorder(scapegoat_tree_t scapegoat,
		void key_handler(void *x, void *context), void *context)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER,);
	_ASSERT(scapegoat->size, <=, 0, EMPTY,);

	_binary_tree_reverse_inorder(scapegoat->root, key_handler, context);
}

void scapegoat_tree_postorder(scapegoat_tree_t scapegoat, void key_handler(
		void *x, void *context), void *context)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER,);
	_ASSERT(scapegoat->size, <=, 0, EMPTY,);

	_binary_tree_postorder(scapegoat->root, key_handler, context);
}

void scapegoat_tree_level_order(scapegoat_tree_t scapegoat, void key_handler(
		void *x, void *context), void *context)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER,);
	_ASSERT(scapegoat->size, <=, 0, EMPTY,);

	_binary_tree_level_order(scapegoat->root, key_handler, context);
}

void scapegoat_tree_show_indented(scapegoat_tree_t scapegoat, void key_handler(
		void *x, int level, void *context), void *context)
{
	_ASSERT(scapegoat, ==, NULL, NULL_POINTER,);
	_ASSERT(scapegoat->size, <=, 0, EMPTY,);

	_binary_tree_show_indented(scapegoat->root, key_handler, context, 0);
}

static void _scapegoat_tree_rebalance(scapegoat_tree_t scapegoat,
		scapegoat_node_t add)
{
	scapegoat_node_t parent = NULL, brother = NULL;
	int side = -1;
	int size = 0, current_size = 1, brother_size = 0;

	parent = _binary_tree_get_parent(add);

	while (parent)
	{
		// In the variable side, i remember the descendent type of
		// current node : left or right.
		if (_binary_tree_get_left_child(parent) == add)
		{
			brother = _binary_tree_get_right_child(parent);
			side = 0;
		}
		else if (_binary_tree_get_right_child(parent) == add)
		{
			brother = _binary_tree_get_left_child(parent);
			side = 1;
		}
		else
			report_error("Internal error, please report !\n");

		brother_size = _binary_tree_get_size(brother);
		size = current_size + brother_size + 1;

		if (current_size > brother_size && current_size > scapegoat->alpha
				* size)
		{
			if (side == 0)
				parent = _self_balanced_binary_search_tree_rotate_right(parent);
			else if (side == 1)
				parent = _self_balanced_binary_search_tree_rotate_left(parent);
			parent = _binary_tree_get_parent(parent);
		}
		else if (current_size < brother_size && brother_size > scapegoat->alpha
				* size)
		{
			if (side == 0)
				parent = _self_balanced_binary_search_tree_rotate_left(parent);
			else if (side == 1)
				parent = _self_balanced_binary_search_tree_rotate_right(parent);
			parent = _binary_tree_get_parent(parent);
		}

		current_size = size;
		add = parent;
		parent = _binary_tree_get_parent(add);
	}

	while (_binary_tree_get_parent(scapegoat->root))
		scapegoat->root = _binary_tree_get_parent(scapegoat->root);
}
